This invention relates to network load balancing. More particularly, this invention relates to a system and a method for table-based hashing for traffic splitting in order to achieve network load balancing.
Load balancing, also known as load sharing, is a basic technique that has been used in networks, for example the Internet, for enhancing network performance and reliability. A typical simple load balancing system has a traffic splitter, an incoming link, and two or more outgoing links. The traffic splitter takes data packets from the incoming traffic link and dispatches the packets onto one of the outgoing links. The traffic to the outgoing links is split into specific proportions.
Many large enterprise networks are connected to multiple Internet Service Providers (ISPs), often referred to as multi-homed. Multiple paths to Internet backbones provide redundant connectivity and the potential to distribute traffic loading effectively and thereby reduce congestion. To achieve high availability, many of the Internet backbones are engineered to have multiple parallel trunks between major points of presence (PoPs). Typically, those parallel trunks are all in service rather than as hot standby so that the utilization during the normal operation can be substantially reduced. Most routing protocols, have mechanisms to allow traffic to be split over multiple equal-cost paths.
The advent of Wavelength Division Multiplexing (WDM) has significantly increased the use of load balancing. WDM expands the capacity of communication trunks by allowing a greater number of channel to be carried on a single optical fiber. With potentially tens or even hundreds of parallel channels between major PoPs, effective load balancing is essential if one is to utilize the expanded capacity efficiently.
With the exponential growth in Internet traffic, parallel architectures offer a scaleable approach for packet processing in routers. Instead of going through a central processing engine, packets can be dispatched to multiple processing engines inside a router to increase the overall processing throughput. The same technique can also apply to Internet servers such as web servers. A router may split the traffic to different ports that are connected to different web servers.
Key to good load balancing is the method that dispatches packets from a traffic stream onto multiple smaller streams. The traffic splitting method determines the efficiency of the load balancing and also the complexity in implementing load balancing in routers.
Inverse multiplexing is a special form of the load balancing that has been extensively studied and widely used in telecommunication networks. Inverse multiplexing allows telecommunications service providers to offer wideband channels by combining multiple narrowband trunks. Inverse multiplexers which operate on 56 kpbs and 64 kbps circuit switched channels are commercially available. Standardization of inverse multiplexers has been started by the BONDING consortium, described in P. Fredette, The Past, Present and Future of Inverse Multiplexing, IEEE Network, April 1995.
Most inverse multiplexing schemes use some form of round robin, or fair queuing, methods to split traffic. Each successive packet is routed according to the round robin protocol, which can lead to packets of a given connection being sent out over different outgoing links. This, however leads to likely misordering of packets at the receiving end because different paths have different delays. In order to maintain synchronization, it is necessary to add extra packet header with sequence numbers or to keep state at each end of the inverse multiplexed channel. Therefore, inverse multiplexing typically operates at data link layer over point-to-point links. Sometimes it is incorporated into a data link layer protocol. For example, Point-to-Point Protocol (PPP) has extended its packet formats to allow inverse multiplexing to be implemented although no algorithm is specified how the inverse multiplexing is performed at either the sending or the receiving side. The misordering of packets triggers a false TCP congestion adjustment, which unnecessarily reduces throughput.
Hashing-based schemes for load balancing have been used in some commercial router products. However, the methods in these products are very simple, typically using the last 2-3 bits of the Internet Protocol (IP) destination address or simple hashing over the IP destination address to distribute traffic over multiple links.
OSPF (Open Shortest Path First) routing protocol has incorporated support for multiple equal-cost paths. However, the algorithms for splitting traffic over multipaths are not specified there. In the OSPF Optimized Multipath protocol (OSPF-OMP), described by Villamizer in “OSPF Optimized Multipath (OSPF-OMP)”, working draft, March 1998, a number of possible approaches for load balancing over multiple paths have been proposed, including per-packet round robin, dividing destination prefixes among available next hops in the forwarding table, and dividing traffic according to a hash function applied to the source and destination pair. However, the actual hash functions for traffic splitting is not defined.
A traffic splitting scheme using random numbers was proposed in D. Thaler, “Multipath Issues in the Unicast and Multicast”, working draft, January 1997. In the scheme, each next-hop is assigned with a weight based on a simple pseudo-random number function seeded with the flow identifier and the next-hop identifier. When a packet arrived and there are N next hops for the destination, the weights are calculated and the next-hop receiving the highest weight is used for forwarding. The scheme is approximately N times as expensive as a hashing-based scheme. Also, no performance studies on the proposed scheme were offered.
What is needed is a fast acting method for network load balancing that distributes traffic over multiple links without misordering of packets, at whatever load proportion that is desired.